package com.wenhao.leetcode.medium;

import java.util.ArrayList;
import java.util.List;

/**
 * 题目：https://leetcode-cn.com/problems/combinations/
 * 组合
 *
 * 题目理解错了，返回的应该是有序的 因为是组合！
 *
 *
 * @author Wenhao Tong
 * @Description
 * @create 2021-06-28 15:33
 */
public class LeetCode77 {

    public static void main(String[] args) {
        LeetCode77 leetCode77 = new LeetCode77();
        List<List<Integer>> lists = leetCode77.combine(4, 2);
        for (List<Integer> list : lists) {
            for (Integer num : list) {
                System.out.print(num + " ");
            }
            System.out.println();
        }
    }

    public List<List<Integer>> combine(int n, int k) {
        boolean[] used = new boolean[n];
        List<Integer> path = new ArrayList<>();
        dfs(0,n,k,1,path);
        return result;
    }

    List<List<Integer>> result = new ArrayList<>();

    private void dfs(int index, int n, int k, int begin,List<Integer> path) {
        if (index == k) {
            result.add(new ArrayList<>(path));
            return;
        }
//        for (int i = begin;i <= n;i++) {
        // 一种优化：至少需要剩下这么多的数字才有可能拼接完整
        for (int i = begin;i <= n - (k - path.size()) + 1;i++) {
            path.add(i);
            dfs(index + 1,n,k,i + 1,path);
            path.remove(path.size() - 1);
        }
    }

}
